package Offer04_二维数组中的查找;

/**
 * ---------------------------------------------------------------------------------------------
 * 题目：
 *      在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 *      请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * ---------------------------------------------------------------------------------------------
 * 示例:
 *      现有矩阵 matrix 如下：
 *      [ [1,  4,  7,  11, 15],
 *        [2,  5,  8,  12, 19],
 *        [3,  6,  9,  16, 22],
 *        [10, 13, 14, 17, 24],
 *        [18, 21, 23, 26, 30] ]
 *      给定 target=5，返回true。
 *      给定 target=20，返回false。
 * ---------------------------------------------------------------------------------------------
 * 方法：
 *      方法1：暴力查找
 *              时间复杂度O(N*M)
 *      方法2：二分查找
 *              时间复杂度O(N+M)
 * ---------------------------------------------------------------------------------------------
 */
class Solution {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(findNumberIn2DArray1(matrix,5));
        System.out.println(findNumberIn2DArray1(matrix,20));
        System.out.println(findNumberIn2DArray2(matrix,5));
        System.out.println(findNumberIn2DArray2(matrix,20));
    }
    public static boolean findNumberIn2DArray1(int[][] matrix, int target) {
        int n=matrix.length;
        if(n==0){
            return false;
        }
        int m=matrix[0].length;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(matrix[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean findNumberIn2DArray2(int[][] matrix, int target) {
        int n=matrix.length;
        if(n==0){
            return false;
        }
        int m=matrix[0].length;
        int i=0;
        int j=m-1;
        while(i<n&&j>=0){
            if(matrix[i][j]<target){
                i++;
            }else if(matrix[i][j]>target){
                j--;
            }else{
                return true;
            }
        }
        return false;
    }
}